#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const long long inf=(1e9+9);
ll** mutiple(ll** a, ll** b, int n) {
    ll** c=new ll*[n];
    for (int i=0; i<n; i++) c[i]=new ll[n];
    ll result;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            result=0;
            for (int k=0; k<n; k++) {
                result=(result+a[i][k]*b[k][j])%inf;
            }
            c[i][j]=result%inf;
        }
    }
    for (int i=0; i<n; i++) delete []a[i];
    return c;
}
int main() {
    ll n;
    scanf("%lld", &n);
    n=n-2;
    ll a[2][2]={1,1,1,0};
    ll **tmp=new ll*[2];
    for (int i=0; i<2; i++) tmp[i]=new ll[2];
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            tmp[i][j]=a[i][j];
    ll **res=new ll*[2];
    for (int i=0; i<2; i++) res[i]=new ll[2];
    for (int i=0; i<2; i++) {
        for (int j=0; j<2; j++) {
            if (i==j) res[i][j]=1;
            else res[i][j]=0;
        }
    }
    while (n) {
        if (n&1) {
            res=mutiple(res,tmp,2);
        }
        tmp=mutiple(tmp,tmp,2);
        n=n>>1;
    }
    printf("%lld\n", (res[0][0]+res[0][1])%inf);
    return 0;
}
